Discrete Mathematics
Q252.
The time complexity of computing the transitive closure of a binary relation on a set of n elements is known to beQ253.
Let R_1 and R_1 be two equivalence relations on a set. Consider the following assertions: I. R_1 \cup R_2 is an equivalence relation II. R_1 \cap R_2 is an equivalence relation Which of the following is correct?Q254.
Let R be the relation on the set of positive integers such that aRb if and only if a and b are distinct and have a common divisor other than 1. Which one of the following statements about R is true?Q255.
Let X be a set and 2^X denote the powerset of X. Define a binary operation \Delta on 2^X as follows:A \Delta B=(A-B) \cup (B-A) Let H=(2^X,\Delta ) . Which of the following statements about H is/are correct?Q256.
If A=\{x, y, z\} and B=\{u, v, w, x\}, and the universe is \{s, t, u, v, w, x, y, z\}. Then (A \cup \bar{B}) \cap(A \cap B) is equal toQ257.
Let S be a set of consisting of 10 elements. The number of tuples of the form (A,B) such that A and B are subsets of S, and A\subseteq B is _______Q258.
Let U=\{1,2,,...n\}. Let A=\{(x,X)|x\in X,X\subseteq U\}. Consider the following two statements on |A|. I. |A|=n2^{n-1}II. |A|=\sum_{k=1}^{n}k\binom{n}{k}Which of the above statements is/are TRUE?Q259.
The following paradigm can be used to find the solution of the problem in minimum time:Given a set of non-negative integer and a value K, determine if there is a subset of the given set with sum equal to K:Q260.
Consider the first order predicate formula: \forall x[\forall z\; z|x\Rightarrow ((z=x)\vee (z=1))\Rightarrow \exists w(w> x)\wedge (\forall z \; z|w\Rightarrow ((w=z)\vee (z=1)))] Here 'a|b' denotes that 'a divides b', where a and b are integers. Consider the following sets: S1: {1, 2, 3, ..., 100} S2: Set of all positive integers S3: Set of all integers Which of the above sets satisfy \varphi ?